# mat = [[0,0,0],[0,1,0],[0,0,0]]
# mat = [[1,0,0],[0,1,0],[1,1,1]]
mat=[[1,0,1,1,0,0,1,0,0,1],[0,1,1,0,1,0,1,0,1,1],[0,0,1,0,1,0,0,1,0,0],[1,0,1,0,1,1,1,1,1,1],[0,1,0,1,1,0,0,0,0,1],[0,0,1,0,1,1,1,0,1,0],[0,1,0,1,0,1,0,0,1,1],[1,0,0,0,1,1,1,1,0,1],[1,1,1,1,1,1,1,0,1,0],[1,1,1,1,0,1,0,0,1,1]]
def updateMatrix(mat):
    direction=[-1,0,1,0,-1]
    #结果矩阵，
    res=[[0 for _ in range(len(mat[0]))] for _ in range(len(mat))]
    #状态矩阵
    is_reach=[[False for _ in range(len (mat[0]))] for _ in range(len(mat))]
    #队列
    queue_list=[]

    for i in range(len(mat)):
        for j in range(len(mat[0])):
            if mat[i][j]==0:
                #存入队列中
                res[i][j] = 0
                is_reach[i][j]=True
                queue_list.append([i,j])
    print(queue_list)
    while queue_list:
        queue_len=len(queue_list)
        index=0
        while index<queue_len:
            [x,y]=queue_list.pop(0)
            for i in range(1,5):
                r=x+direction[i]
                c=y+direction[i-1]
                if r<len(mat) and  r>=0 and c<len(mat[0]) and c>=0 and is_reach[r][c]==False:
                    is_reach[r][c]=True
                    res[r][c]=res[x][y]+1
                    queue_list.append([r,c])
            index+=1

    print(res)
###动态规划
def updateMatrix_1(mat):
    #行数和列数
    mat_row_len=len(mat)
    mat_col_len=len(mat[0])
    dp=[[0 for _ in range(mat_col_len)] for _ in range(mat_row_len)]
    max=mat_col_len*mat_row_len
    for i in range(mat_row_len):
        for j in range(mat_col_len):
            if mat[i][j]!=0:
                min_value=max
                if i>0 and i<mat_row_len and min_value>dp[i-1][j]:
                    min_value=dp[i-1][j]
                if j>0 and j<mat_col_len and min_value>dp[i][j-1]:
                    min_value=dp[i][j-1]
                dp[i][j]=min_value+1
    # print(dp)
    i=mat_row_len-1
    while i>=0:
        j=mat_col_len-1
        while j>=0:
            if mat[i][j]!=0:
                if i<mat_col_len-1 and i>=0:
                    dp[i][j]=min(dp[i][j],dp[i+1][j]+1)
                if j<mat_row_len-1 and j>=0:
                    dp[i][j]=min(dp[i][j],dp[i][j+1]+1)
            j-=1
        i-=1

    print(dp)
    pass
updateMatrix_1(mat)